package com.ch;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author chenhong
 * @version 1.0.0
 * @ClassName 下一个更大元素_II.java
 * @Description TODO
 * @createTime 2021年03月06日 11:39:00
 */
public class 下一个更大元素_II {
}

//暴力遍历
class Solution503 {
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            int j;
            for (j = 1; j < len; j++) {
                if (nums[(i + j) % len] > nums[i]) {
                    ans[i] = nums[(i + j) % len];
                    break;
                }
            }
            if (j == len) {
                ans[i] = -1;
            }
        }
        return ans;

    }
}

class Solution503_2 {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n * 2 - 1; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ret[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);
        }
        return ret;
    }
}

